TNotes.leetcode

Appearance

0066. 加一【简单】

0066. 加一【简单】 ​

1. 📝 题目描述 ​

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1, 2, 3]
输出：[1, 2, 4]

解释：输入数组表示数字 123。

示例 2：

输入：digits = [4, 3, 2, 1]
输出：[4, 3, 2, 2]

解释：输入数组表示数字 4321。

示例 3：

输入：digits = [9]
输出：[1, 0]

解释：

  • 输入数组表示数字 9。
  • 加 1 得到了 9 + 1 = 10。
  • 因此，结果应该是 [1, 0]。

提示：

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

2. 🎯 s.1 - 逆序循环 ​

js
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
  const len = digits.length

  // 处理加一
  // 下面两种写法都 OK

  // 写法 1：
  // for (let i = len - 1; i >= 0; i--) {
  //   digits[i]++
  //   digits[i] %= 10
  //   // 如果某位加一后不为 0（没有进位）则直接返回
  //   if (digits[i] !== 0) return digits
  // }

  // 写法 2：
  for (let i = len - 1; i >= 0; i--) {
    if (digits[i] === 9) {
      digits[i] = 0
    } else {
      // 当前位不是 9，加 1 后直接返回
      digits[i]++
      return digits
    }
  }

  // 如果所有位都需要进位（全为 9），则创建新数组并将首位设为 1
  // 下面两种写法都 OK

  // 写法 1：
  // const result = Array(len + 1).fill(0)
  // result[0] = 1
  // return result

  // 写法 2：
  digits.unshift(1)
  return digits
}
  • 时间复杂度：O(n)，其中 n 是数组长度，最坏情况下需要遍历整个数组
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

算法思路：

  • 写法 1：从数组末尾开始逐位加一并取模 10。如果某位加一后不为 0（没有进位）则直接返回；如果所有位都需要进位（全为 9），则创建新数组并将首位设为 1。
  • 写法 2：从数组末尾开始遍历，遇到 9 就置为 0 继续进位，遇到非 9 就加一后直接返回。如果所有位都是 9，则在数组开头插入 1。

两种写法的核心思路是一样的，都是处理进位问题。

Discussions